/*
 * 8.8
 * Write an algorithm to print all ways of arranging eight queens on a chess board so
 * that none of them share the same row, column or diagonal.
 */
#include <stdio.h>

const int n = 8;
int l2r[n*2-1], r2l[n*2-1];
int result[n]; // result count is 92 when n is 8, unique solution count is 12 and need more work...
int count;

void queen(int i)
{
    if (i == n) {
        for (int j = 0; j < n; j++) {
            printf("%d ", result[j]);
        }
        count++;
        printf("\n");
        return;
    }
    for (int j = 0; j < n; j++) {
        bool find = false;
        for (int k = 0; k < i; k++) {
            if (result[k] == j) {
                find = true;
                break;
            }
        }
        if (!find) {
            if (!r2l[i+j] && !l2r[i-j+n]) {
                result[i] = j;
                // mark
                r2l[i+j] = 1;
                l2r[i-j+n] = 1;
                // backtracking
                queen(i+1);
                // unmark
                r2l[i+j] = 0;
                l2r[i-j+n] = 0;
            }

        }
    }
}

void queen2(int i)
{
    if (i == n) { // XXX: was i+1 == n...
        for (int j = 0; j < n; j++) {
            printf("%d ", result[j]);
        }
        count++;
        printf("\n");
        return;
    }
    for (int j = 0; j < n; j++) {
        bool valid = true; // XXX: initial to true and check valid, not working in reverse check when i is 0.
        for (int k = 0; k < i; k++) {
            if (result[k] == j || (k+result[k] == i+j) || (k-result[k] == i-j)) {
                valid = false;
                break;
            }
        }
        if (valid) {
            result[i] = j;
            queen2(i+1);
        }
    }
}

int main()
{
    queen2(0);
    printf("count=%d\n", count);
    return 0;
}
